package com.booby.algorithm.count;

import com.booby.algorithm.utils.Utils;

/**
 * 功能描述: 计数排序，优化稳定版本
 *
 * @author: lizt
 * @date: 2020/8/28 09:15
 **/

public class OptimizedVersion {

    public static Integer[] arr = {2, 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 9, 8, 5, 7, 4, 0, 9};
    public static final int MIN = 0;
    public static final int MAX = 9;

    public static void sorted(Integer[] arr){
        Integer[] count = new Integer[MAX - MIN + 1];
        // 初始化为0
        for (int i = 0; i < count.length; i++) {
            count[i] = 0;
        }
        // 计算每个值出现的次数
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] - MIN;
            count[index]++;
        }
        // 计算出count数据值每个值相对首元素的和的值
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i-1];
        }
        Integer[] temp = new Integer[arr.length];
        for (int i = arr.length -1; i >= 0; i--) {
            // 原数组中的该数在count数组中的位置
            int countIndex = arr[i] - MIN;
            // 当前该数在arr中的位置
            int arrIndex = count[countIndex] - 1;
            temp[arrIndex] = arr[i];
            count[countIndex]--;
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = temp[i];
        }
    }


    public static void main(String[] args) {
        sorted(arr);
        Utils.print(arr);
    }
}
